package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DivideConquer;
import cn.pugle.oj.catalog.Unknown;

import java.util.Arrays;

/**
 * 扫一遍就O(n)了, 比二分的logn呆
 *
 * @author tzp
 * @since 2020/10/20
 */
public class LC33 implements DivideConquer {

    public int search(int[] nums, int target) {
        int breakPoint = -1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) {
                breakPoint = i;
                break;
            }
        }
        if (breakPoint != -1) {
            int i = Arrays.binarySearch(nums, 0, breakPoint, target);
            if (i < 0) {
                i = Arrays.binarySearch(nums, breakPoint, nums.length, target);
            }
            return i < 0 ? -1 : i;
        } else {
            int i = Arrays.binarySearch(nums, target);
            return i < 0 ? -1 : i;
        }
    }

    public static void main(String[] args) {
        System.out.println(new LC33().search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0));
    }
}
